package sort;

import java.util.ArrayList;
import java.util.List;

public class ShellSort {

    public static <T extends Comparable> List<T> sort(List<T> nums) {
        // 1. 复制数组
        List<T> result = new ArrayList<>(nums);
        // 2. 排序，外层循环控制步长
        for (int d = result.size() / 2; d > 0; d /= 2) {
            //2.1 控制每层循环的起始位置
            for (int i = 0; i < d; i++) {
                // 插入排序
                for (int j = i; j < result.size(); j += d) {
                    int min = j;
                    for (int k = j + d; k < result.size(); k++) {
                        if (result.get(k).compareTo(result.get(min)) < 0) {
                            min = k;
                        }
                    }
                    if (min != j) {
                        T tmp = result.get(min);
                        result.set(min, result.get(j));
                        result.set(j, tmp);
                    }
                }
            }
        }
        return result;
    }
}
